package leetcode.dynamic;

import java.util.*;

/**
 * @author: 26233
 * @create: 2022-03-27 13:36:01
 * @Description
 *
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 *
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 *
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 *  
 *
 * 示例：
 *
 * 输入：[[1,2], [2,3], [3,4]]
 * 输出：2
 * 解释：最长的数对链是 [1,2] -> [3,4]
 *  
 *
 * 提示：
 *
 * 给出数对的个数在 [1, 1000] 范围内。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 解法：
 *  1. 贪心：
 *      a. 将paris的第二个数字来排序然后寻找最长的数对
 **/

public class LeetCode646_FindLongestChain {

    public int findLongestChain(int[][] pairs) {

        if (pairs == null || pairs.length < 1) return 0;

        Map<Integer, List<Integer[]>> m = new HashMap<>();
        for(int[] x : pairs){
            if(m.containsKey(x[1])){
                m.get(x[1]).add(new Integer[]{x[0], x[1]});
            }else {
                List<Integer[]> l = new ArrayList<>();
                l.add(new Integer[]{x[0], x[1]});
                m.put(x[1], l);
            }
        }

        List<Integer> k = new ArrayList<>(m.keySet());
        k.sort(Comparator.naturalOrder());

        int r = 0;
        int t = 0;
        boolean start = true;
        for(Integer x : k){
            m.get(x).sort(Comparator.comparingInt(a -> -a[0]));
            if(start){
                r++;
                t = m.get(x).get(0)[1];
                start = false;
            }else {
                if(m.get(x).get(0)[0] > t){
                    t = m.get(x).get(0)[1];
                    r++;
                }
            }
        }

        return r;
    }

    public static void main(String[] args) {
        // int[][] p = new int[][]{{1, 2}, {2, 3}};
        // int[][] p = new int[][]{{-6,9},{1,6},{8,10},{-1,4},{-6,-2},{-9,8},{-5,3},{0,3}};
        int[][] p = new int[][]{{-10,-8},{8,9},{-5,0},{6,10},{-6,-4},{1,7},{9,10},{-4,7}};
        System.out.println(new LeetCode646_FindLongestChain().findLongestChain(p));
    }


}
